package LeetCodeHot100TopInterview;

import java.util.PriorityQueue;

public class Q215_KthNumInArray {

    //在未排序的数组中找到第 k 个最大的元素。
    //请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
    //不能排序 ==> O(N)
    public int findKthLargest(int[] nums, int k) {

        //小根堆?  ==> O(logN + K) < O(N)  空间 0(K) ==> 堆内元素的大小 综合来看 是最优解
        //默认小根堆
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);

        for (int i = 0; i < nums.length; i++) {
            if (minHeap.size() < k){
                minHeap.add(nums[i]);
            }else {
                if (nums[i] > minHeap.peek()){
                    minHeap.poll();
                    minHeap.add(nums[i]);
                }
            }
        }
        //要第k个  去掉k - 1 个
        int[] kArr = new int[minHeap.size()];
        for (int i = kArr.length - 1; i > -1;  i--) {
            kArr[i] = minHeap.poll();
        }
        return kArr[k - 1];
    }

    public static void main(String[] args) {
        Q215_KthNumInArray fun = new Q215_KthNumInArray();
        System.out.println(fun.findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }
}
